#include <iostream>

// 借助堆排序：堆扫描快
// 先有数据结构，从前往后插入； 先有数列，从后往前构建数据结构；

// 构建一个堆 最大堆  // 从后往前构建  从下往上构建
void MakeHeap(int *a, int n, int index) // 以index为根构建最大堆
{
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int max = index;
    if (left < n && a[left] > a[max]) // 下沉的操作
    {
        max = left;
    }
    if (right < n && a[right] > a[max])
    {
        max = right;
    }
    if (max != index)
    {
        std::swap(a[max], a[index]);
        MakeHeap(a, n, max);
    }
}

// 每次前面的构建最大堆，把根放到最后，然后继续构建最大堆，把根放最后
// 和选择排序原理差不多
void HeapSort(int *a, int n) // nlogn
{
    // for(int i = n - 1;i >= 0;i--)
    // {
    //     MakeHeap(a,n,i);
    // }

    // 一颗完全二叉树叶子数：n/2 + 1;
    for (int i = n / 2 - 1; i >= 0; i--) // 从最后一个非叶子结点构建  // for(int i = n - 1;i >= 0;i--)
    {
        MakeHeap(a, n, i); // 从后往前依次构建
    }
    for (int i = n - 1; i > 0; i--)
    {
        std::swap(a[0], a[i]); // 把最大值放最后
        MakeHeap(a, i, 0);   // 剩下的继续构建堆
    }
}

int main()
{
    int a[5] = {5, 1, 2, 6, 3};
    HeapSort(a, 5);
    for (int i = 0; i < 5; i++)
    {
        std::cout << a[i] << " ";
    }
    return 0;
}
